Minimum absolute difference

Time: O(NLogN); Space: O(N); easy

Given an array of distinct integers arr, find all pairs of elements with the minimum absolute difference of any two elements.

Return a list of pairs in ascending order(with respect to pairs), each pair [a, b] follows: * a, b are from arr * a < b * b - a equals to the minimum absolute difference of any two elements in arr

Example 1:

Input: arr = [4,2,1,3]

Output: [[1,2],[2,3],[3,4]]

Explanation:

• The minimum absolute difference is 1.

• List all pairs with difference equal to 1 in ascending order.

Example 2:

Input: arr = [1,3,6,10,15]

Output: [[1,3]]

Example 3:

Input: arr = [3,8,-10,23,19,-4,-14,27]

Output: [[-14,-10],[19,23],[23,27]]

Notes:

• 2 <= len(arr) <= 10^5

• -10^6 <= arr[i] <= 10^6

class Solution1(object):
    def minimumAbsDifference(self, arr):
        """
        :type arr: List[int]
        :rtype: List[List[int]]
        """
        result = []
        min_diff = float("inf")
        arr.sort()
        for i in range(len(arr)-1):
            diff = arr[i+1]-arr[i]
            if diff < min_diff:
                min_diff = diff
                result = [[arr[i], arr[i+1]]]
            elif diff == min_diff:
                result.append([arr[i], arr[i+1]])
        return result

s = Solution1()
arr = [4,2,1,3]
assert s.minimumAbsDifference(arr) == [[1,2],[2,3],[3,4]]
arr = [1,3,6,10,15]
assert s.minimumAbsDifference(arr) == [[1,3]]

See also:

https://leetcode.com/problems/minimum-absolute-difference